#include "circuitgraph.h"

void CircuitGraph :: readSizerFile(std::ifstream& in)
{
        
        this->clearTouchedFlag();
        char buffer[256];
        
        while(in.getline(buffer,256))
        {
                string instanceName = strtok(buffer, " ");
                string cellName = strtok(NULL, " \n");
                
                boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
                for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi)
                {
                        if((*this)[*vi].gateType != 2 || (*this)[*vi].touched == 1)
                                continue;
                
                        if((*this)[*vi].instanceName == instanceName)
                        {
                                (*this)[*vi].cellName = cellName;
                                (*this)[*vi].touched = 1;
                                break;
                        }
                }
        }    
}


double CircuitGraph::findMinTotalOutputCapacitance(vertex_descriptor currNode, ExtendedLibParser& library)
{

        boost::graph_traits<CircuitGraph>::out_edge_iterator oi, oi_end ;
        
        double totalCap = 0.0 ;
        double netCap ;
        
        for (boost::tie(oi, oi_end) = boost::out_edges(currNode, (*this)) ; oi != oi_end ; ++oi)
        {
                vertex_descriptor targetNode = boost::target((*oi), (*this)) ;
                std::string targetPinName = (*this)[(*oi)].targetPinName ;
                
                netCap = (*this)[(*oi)].netParasiticLoad ;
                
                if ( (*this)[targetNode].visited == 1 )
                {
                        totalCap += library.getInputCapacitance( (*this)[targetNode].cellName, targetPinName ) ;
                }
                else
                {
                        totalCap += library.getMinInputCapacitance ( (*this)[targetNode].footPrint, targetPinName ) ; 
                }
        }

        return totalCap + netCap ;

}


void CircuitGraph::clearTouchedFlag()
{
        boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
        for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi)
                (*this)[*vi].touched = 0;
}


void CircuitGraph::clearIsFixedFlag()
{

	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	
	for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi)
	{
		if ((*this)[*vi].gateType == Combinational)
			(*this)[*vi].isFixed = false ;
	}

}


double CircuitGraph::calTotalNegativeSlacksTimesFanout(vertex_descriptor currNode, ExtendedLibParser& library, ExtendedTimingParser& timing)
{

	// used in phase 1
	double totalNS = 0.0 ;
	
	boost::graph_traits<CircuitGraph>::out_edge_iterator oi, oi_end ;
	
	for ( boost::tie(oi, oi_end) = boost::out_edges(currNode,(*this)) ; oi != oi_end; ++oi )
	{
		vertex_descriptor targetNode = boost::target((*oi), (*this)) ;
		std::string targetPinName = (*this)[(*oi)].targetPinName ; 
		
		std::string timingLookup = (*this)[targetNode].instanceName + "/" + targetPinName ;
		totalNS += std::max(0.0, -std::max(timing.PinsTiming[timingLookup].riseSlack , 
                                                   timing.PinsTiming[timingLookup].fallSlack ) ) ;
	}
	if ((*this)[currNode].distance == 0)
		cout << "No way!!!!" << "ERROR...>>>>>>>!#@$!!%%!%!%!!^!!&@*$^*(&^*%" << endl ;
	return  ( (totalNS) * (double)boost::out_degree(currNode, (*this))) / (*this)[currNode].distance ;
}


double CircuitGraph::calTotalNegativeSlacksPerFanout(vertex_descriptor currNode, ExtendedLibParser& library, ExtendedTimingParser& timing)
{
	double totalNS = 0.0 ;
	
	// used in phase 2
	boost::graph_traits<CircuitGraph>::out_edge_iterator oi, oi_end ;
	
	for ( boost::tie(oi, oi_end) = boost::out_edges(currNode,(*this)) ; oi != oi_end; ++oi )
	{
		vertex_descriptor targetNode = boost::target((*oi), (*this)) ;
		std::string targetPinName = (*this)[(*oi)].targetPinName ; 
		
		std::string timingLookup = (*this)[targetNode].instanceName + "/" + targetPinName ;
		totalNS += std::max(0.0, -std::max(timing.PinsTiming[timingLookup].riseSlack , 
                                                   timing.PinsTiming[timingLookup].fallSlack ) ) ;
	}
	if ((*this)[currNode].distance == 0)
		cout << "No way!!!!" << "ERROR...>>>>>>>!#@$!!%%!%!%!!^!!&@*$^*(&^*%" << endl ;
	return  ( (totalNS) ) / ( (*this)[currNode].distance * (double)boost::out_degree(currNode, (*this)) ) ;
}


int CircuitGraph::fixCones(vertex_descriptor currNode)
{
	boost::graph_traits<CircuitGraph>::out_edge_iterator oi, oi_end ;
	
	if ((*this)[currNode].gateType == Sequential || (*this)[currNode].gateType == PrimaryOutput)
		return 1 ;
	
	for ( boost::tie(oi, oi_end) = boost::out_edges(currNode,(*this)) ; oi != oi_end; ++oi )
	{
		vertex_descriptor targetNode = boost::target((*oi), (*this)) ;
		
		(*this)[targetNode].isFixed = true ;
		
		//cout << (*this)[targetNode].instanceName << " is fixed" << endl ;
		this->fixCones(targetNode) ;
	}
	
	return 1 ;
}


double CircuitGraph::calTotalPositiveSlacksPerFanout(vertex_descriptor currNode, ExtendedLibParser& library, ExtendedTimingParser& timing)
{

	double totalPS = 0.0 ;
	
	boost::graph_traits<CircuitGraph>::out_edge_iterator oi, oi_end ;
	
	for ( boost::tie(oi, oi_end) = boost::out_edges(currNode,(*this)) ; oi != oi_end; ++oi )
	{
		vertex_descriptor targetNode = boost::target((*oi), (*this)) ;
		std::string targetPinName = (*this)[(*oi)].targetPinName ; 
		
		std::string timingLookup = (*this)[targetNode].cellName + "/" + targetPinName ;
		
		totalPS += std::max(timing.PinsTiming[timingLookup].riseSlack , 
                                    timing.PinsTiming[timingLookup].fallSlack ) ;
	}
	
	//cout << "Degree: " << boost::out_degree(currNode, (*this)) << endl ;
	return (totalPS) * (*this)[currNode].level;
	
}


void CircuitGraph::updateSortedNoCapViolation(ExtendedLibParser& library)
{
	std::vector<std::string>::iterator it ;
	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	
	for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi)
	{
		if ((*this)[(*vi)].gateType == Combinational)
		{
			for (it = (*this)[(*vi)].noCapViolationCells.begin() ; it != (*this)[(*vi)].noCapViolationCells.end() ; ++it)
			{
                                GateDelayStructure tmpGateDelay ;	 
                                tmpGateDelay.cellName  = (*it);
                                tmpGateDelay.avgDelay  = library.findMaxAvgDelay((*it));
                                tmpGateDelay.leakagePower = library.mapStandardLibraryCells[(*it)].leakagePower ;
                                (*this)[(*vi)].sortedNoCapViolation.push_back(tmpGateDelay) ;
			}
			std::sort((*this)[(*vi)].sortedNoCapViolation.begin(), (*this)[(*vi)].sortedNoCapViolation.end(), delayPerLeakageSorting()) ;
			(*this)[(*vi)].previousIndex = 0 ;
		}
		
	}	
}



/*double CircuitGraph::sortBestDelay(vertex_descriptor currNode, ExtendedLibParser& library, ExtendedTimingParser& timing)
  {

  boost::graph_traits<CircuitGraph>::in_edge_iterator ie, ie_end ;
  std::vector<std::string>::iterator noCapIt ;
	
	
  std::map<std::string, double> inputTransitions ;
	
  for (noCapIt = (*this)[currNode].noCapViolationCells.begin() ; noCapIt != (*this)[currNode].noCapViolationCells.end() ; ++noCapIt)
  { 
  for ( boost::tie(ie, ie_end) = boost::in_edges(currNode, (*this)) ; ie != ie_end ; ++ie )
  {
  vertex_descriptor sourceNode = boost::source((*ie), (*this)) ;
			
  std::string sourceInstanceName = (*this)[sourceNode].instanceName ;
  std::string sourceCellName = (*this)[sourceNode].cellName ;
			
  double deltaCap = library.getInputCapacitance( (*noCapIt), (*this)[(*ie)].targetPinName ) 
  - library.getInputCapacitance( (*this)[currNode].cellName, (*this)[(*ie)].targetPinName );
								
  double newCap = this->calculateTotalOutputCap (sourceNode, library) + deltaCap ;
  double maxTrans = library.findMaxTransition( sourceInstanceName, sourceCellName, timing, newCap) ;
  inputTransition[(*this)[(*ie)].targetPinName] = maxTrans ;
  }
		
  double outCap = this->calculateTotalOutputCap (currNode, library) ;
		
  library.findMaxDelay ( (*noCapIt), outCap,  inputTransitions) ;
	
  GateDelayStructure tmpGateDelay ;	 
  tmpGateDelay.cellName  = (*it);
  tmpGateDelay.avgDelay  = library.findMaxAvgDelay((*it));
  tmpGateDelay.leakagePower = library.mapStandardLibraryCells[(*it)].leakagePower ;
  (*this)[(*vi)].sortedNoCapViolation.push_back(tmpGateDelay) ;	
  }
  }
*/

int CircuitGraph::updateVertexLevels(vertex_descriptor currNode, int inputLevel, bool isUpdate)
{

	if ((*this)[currNode].gateType == Sequential || (*this)[currNode].gateType == PrimaryInput)
		return inputLevel ;
		
	boost::graph_traits<CircuitGraph>::in_edge_iterator ie, ie_end ;
	int minLevel = 1000000 ;
	
	for (boost::tie(ie, ie_end) = boost::in_edges((currNode), (*this)) ; ie != ie_end; ++ie)
	{
		vertex_descriptor preVertex ;
		preVertex = boost::source((*ie), (*this)) ;		
		minLevel = std::min(this->updateVertexLevels(preVertex, inputLevel+1, false), minLevel) ;
	}
	
	if (isUpdate)
	{
		(*this)[currNode].level = minLevel ;
		return 0 ;
	}
	else
		return minLevel ;
	
}
	

int CircuitGraph::updateVertexDistance(vertex_descriptor currNode, int inputDistance, bool isUpdate)
{

	if ((*this)[currNode].gateType == Sequential || (*this)[currNode].gateType == PrimaryOutput)
		return inputDistance ;
		
	boost::graph_traits<CircuitGraph>::out_edge_iterator oe, oe_end ;
	int maxDistance = 1000000 ;
	
	for (boost::tie(oe, oe_end) = boost::out_edges((currNode), (*this)) ; oe != oe_end; ++oe)
	{
		vertex_descriptor postVertex ;
		postVertex = boost::target((*oe), (*this)) ;		
		maxDistance = std::max(this->updateVertexDistance(postVertex, inputDistance+1, false), maxDistance) ;
	}
	
	if (isUpdate)
	{
		(*this)[currNode].distance = maxDistance ;
		return 0 ;
	}
	else
		return maxDistance ;

}	

			
void CircuitGraph::updateLevelDistance()
{
	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi)
	{
		if ((*this)[(*vi)].gateType == Combinational)
		{			
			this->updateVertexLevels((*vi), 0 , true) ;
			this->updateVertexDistance((*vi), 0 , true) ;
		}
	}
}


// set to maximum delay
void CircuitGraph::updateSizes()
{
	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi)
	{
		if ((*this)[(*vi)].gateType == Combinational)
		{
			(*this)[(*vi)].cellName = (*this)[(*vi)].sortedNoCapViolation[0].cellName ;
		}
	}
}


void CircuitGraph::updateNodeSlackVector(ExtendedLibParser& library, ExtendedTimingParser& timing, bool isFirst)
{
	this->nodeSlackVector.clear() ;
	
	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	
	for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi)
	{
		if((*this)[(*vi)].gateType == Combinational)
		{
			NodeSlackStruct tmpSlack ;
			tmpSlack.vertexDescriptor = (*vi) ;
			tmpSlack.negativeSlack = (isFirst) ? this->calTotalNegativeSlacksTimesFanout((*vi),library, timing):
                                this->calTotalNegativeSlacksPerFanout((*vi),library, timing) ;
			this->nodeSlackVector.push_back(tmpSlack) ;
		}
	}
	
	std::sort(this->nodeSlackVector.begin(), this->nodeSlackVector.end(), sortingFunction()) ;
}


void CircuitGraph::updatePosititveNodeSlackVector(ExtendedLibParser& library, ExtendedTimingParser& timing)
{
	this->nodeSlackVector.clear() ;
	
	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	
	for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi)
	{
		if((*this)[(*vi)].gateType == Combinational)
		{
			NodeSlackStruct tmpSlack ;
			tmpSlack.vertexDescriptor = (*vi) ;
			tmpSlack.negativeSlack = this->calTotalPositiveSlacksPerFanout((*vi),library, timing) ;
			this->nodeSlackVector.push_back(tmpSlack) ;
		}
	}
	
	std::sort(this->nodeSlackVector.begin(), this->nodeSlackVector.end(), sortingFunction()) ;
}


int CircuitGraph::upsizeCells(double percentage, int& numberofCellChanged, ofstream& cellChange)
{
	std::vector<NodeSlackStruct>::iterator it ;
	
	int maxIndex = this->nodeSlackVector.size() * percentage ;
	
	int i = 0;
	
	for (it = this->nodeSlackVector.begin() ; it != this->nodeSlackVector.end() ; ++it)
	{
		if ((*this)[(*it).vertexDescriptor].isFixed == false)
		{
			cellChange << (*this)[(*it).vertexDescriptor].instanceName << " is changed!!!" << endl ;
			(*this)[(*it).vertexDescriptor].cellName.assign(this->nextCell((*it).vertexDescriptor)) ;
			this->fixCones((*it).vertexDescriptor) ;
			i++ ;
			if (i == maxIndex)
				break ;
		}
	}
	
	numberofCellChanged = i ;
	return this->nodeSlackVector.size() ;
}


void CircuitGraph::printNodeSlackVector()
{
	for (int i = 0 ; i < this->nodeSlackVector.size() ; i++)
	{
		cout << (*this)[this->nodeSlackVector[i].vertexDescriptor].instanceName << "\t" << this->nodeSlackVector[i].negativeSlack << endl ;
	}
}


double CircuitGraph::calculateCapViolation(vertex_descriptor currNode, ExtendedLibParser& library)
{
	boost::graph_traits<CircuitGraph>::out_edge_iterator oi, oi_end ;
	
	double maxCap  = library.findMaxOutputCapacitance((*this)[currNode].cellName) ;
		
	double netCap = 0.0 ;
	double totalCap = 0.0 ;
	
	for ( boost::tie(oi, oi_end) = boost::out_edges(currNode,(*this)) ; oi != oi_end; ++oi )
	{
		vertex_descriptor target = boost::target( (*oi), (*this) ) ;
		std::string pinTarget = (*this)[(*oi)].targetPinName ;
		std::string targetNode = (*this)[target].cellName ;
		if((*this)[target].gateType == PrimaryOutput)
		{
			//cout << "Primary Outputs: " << (*this)[target].outCapacitance << endl ;
			totalCap += (*this)[target].outCapacitance ;
		}
		else
			totalCap += library.getInputCapacitance(targetNode, pinTarget) ;
		netCap = (*this)[(*oi)].netParasiticLoad ;
	}
	
	return std::max(0.0, totalCap + netCap - maxCap) ;
}


double CircuitGraph::calculateTotalCapViolation(ExtendedLibParser& library, ofstream& capViolation)
{
	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	
	double totalCap = 0.0 ;
	
	for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi)
	{
		if((*this)[(*vi)].gateType == Combinational || (*this)[(*vi)].gateType == Sequential)
		{
			double tmpCap = this->calculateCapViolation((*vi), library) ;
			if (tmpCap > 0) 
				capViolation << (*this)[(*vi)].instanceName + "/o\t" << tmpCap << "\t" <<(*this)[(*vi)].cellName <<   endl ;
			totalCap += tmpCap ;
		}
	}
	
	return totalCap ;
}


void CircuitGraph::downSize(double percentage, int& numberofCellChanged)
{
	std::vector<NodeSlackStruct>::iterator it ;
	
	int maxIndex = this->nodeSlackVector.size() * percentage ;
	
	int i = 0;
	
	for (it = this->nodeSlackVector.begin() ; it != this->nodeSlackVector.end() ; ++it)
	{
		if ((*it).negativeSlack > 0) ;
		{
			(*this)[(*it).vertexDescriptor].cellName.assign(this->previousCell((*it).vertexDescriptor)) ;	
			i++ ;
			if (i == maxIndex)
				break ;
		}
	}
	
	numberofCellChanged = maxIndex ;
}


void CircuitGraph::upSizeCap(ExtendedLibParser& library, bool& noCap)
{
	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	
	noCap = true ;
	
	for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi)
	{
		if((*this)[(*vi)].gateType == Combinational)
		{
			if ( this->calculateCapViolation((*vi), library) > 0)
			{
				
				noCap = false ;
				(*this)[(*vi)].cellName.assign(this->nextCell((*vi))) ;
			}
			
		}
	}
}


std::string CircuitGraph::nextCell(vertex_descriptor currNode)
{

	if ((*this)[currNode].previousIndex == (*this)[currNode].listOfCells.size() - 1)
		return (*this)[currNode].listOfCells[(*this)[currNode].previousIndex] ;
	else
	{
		(*this)[currNode].previousIndex++ ;
		return (*this)[currNode].listOfCells[(*this)[currNode].previousIndex] ;
	}
}


std::string CircuitGraph::previousCell(vertex_descriptor currNode)
{
	if ((*this)[currNode].previousIndex == 0)
		return (*this)[currNode].listOfCells[(*this)[currNode].previousIndex] ;
	else
	{
		(*this)[currNode].previousIndex-- ;
		return (*this)[currNode].listOfCells[(*this)[currNode].previousIndex] ;
	}


}


//--------------------------------Amir's-----------------------------------
// std::string CircuitGraph::nextCell(vertex_descriptor currNode)
// {

// 	if ((*this)[currNode].previousIndex == (*this)[currNode].sortedNoCapViolation.size() - 1)
// 		return (*this)[currNode].sortedNoCapViolation[(*this)[currNode].previousIndex].cellName ;
// 	else
// 	{
// 		(*this)[currNode].previousIndex++ ;
// 		return (*this)[currNode].sortedNoCapViolation[(*this)[currNode].previousIndex].cellName ;
// 	}
// }


// std::string CircuitGraph::previousCell(vertex_descriptor currNode)
// {
// 	if ((*this)[currNode].previousIndex == 0)
// 		return (*this)[currNode].sortedNoCapViolation[(*this)[currNode].previousIndex].cellName ;
// 	else
// 	{
// 		(*this)[currNode].previousIndex-- ;
// 		return (*this)[currNode].sortedNoCapViolation[(*this)[currNode].previousIndex].cellName ;
// 	}
// }
//--------------------------------Amir's-----------------------------------

void CircuitGraph::fillBestSolution()
{
	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	
	for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end; vi++)
	{
		if ((*this)[(*vi)].gateType == Combinational)
			this->bestSolution[(*vi)] = (*this)[(*vi)].cellName ;
	}
}


void CircuitGraph::downloadBestSolution()
{
	std::map<vertex_descriptor, std::string>::iterator bi ;
	for(bi = this->bestSolution.begin() ; bi != this->bestSolution.end() ; ++bi)
	{
		(*this)[bi->first].cellName = bi->second ;
	}
}


void CircuitGraph::fillCellSizes()
{
	this->cellSizes.push_back("s01") ;
	this->cellSizes.push_back("s02") ;
	this->cellSizes.push_back("s03") ;
	this->cellSizes.push_back("s04") ;
	this->cellSizes.push_back("s06") ;
	this->cellSizes.push_back("s08") ;
	this->cellSizes.push_back("s10") ;
	this->cellSizes.push_back("s20") ;
	this->cellSizes.push_back("s40") ;
	this->cellSizes.push_back("s80") ;
	
	
	
	this->cellSizes.push_back("m01") ;
	this->cellSizes.push_back("f01") ;
	
	
	this->cellSizes.push_back("m02") ;
	this->cellSizes.push_back("f02") ;
	
	
	this->cellSizes.push_back("m03") ;
	this->cellSizes.push_back("f03") ;
	
	
	this->cellSizes.push_back("m04") ;
	this->cellSizes.push_back("f04") ;
	
	
	this->cellSizes.push_back("m06") ;
	this->cellSizes.push_back("f06") ;
	
	
	this->cellSizes.push_back("m08") ;
	this->cellSizes.push_back("f08") ;
	
	
	this->cellSizes.push_back("m10") ;
	this->cellSizes.push_back("f10") ;
	
	
	this->cellSizes.push_back("m20") ;
	this->cellSizes.push_back("f20") ;
	
	
	this->cellSizes.push_back("m40") ;
	this->cellSizes.push_back("f40") ;
	
	
	this->cellSizes.push_back("m80") ;
	this->cellSizes.push_back("f80") ;	
}


void CircuitGraph::sampleGateAngleGreedy (vertex_descriptor currNode, ExtendedLibParser& library, int Nsample, std::vector<std::string>& samples
                                          , double minDelay, double maxDelay, bool& equal)
{
	samples.clear() ;

        double minTotalCap = this->findMinTotalOutputCapacitance(currNode, library) ;
        //cout << "min total capacitance: " << minTotalCap << endl ;    
        std::vector<std::string>::iterator it ;
    
        if ( (*this)[currNode].gateType == Combinational )
        {

                double min = (*this)[currNode].minDelayLeakage ;
                double max = (*this)[currNode].maxDelayLeakage ;
                double minDelayAvg = (*this)[currNode].minDelayAvg ;
                double maxDelayAvg = (*this)[currNode].maxDelayAvg ;
            
                double stepVal = ((max+0.1) - min) / (double) Nsample ;
                std::vector<RegionStruct> region(Nsample) ;
                std::vector<GateDelayStructure> allGates ;
            
                for (int i = 0 ; i < (int)region.size() ; ++i)
                {
                        region[i].minBound = min ;
                        region[i].maxBound = min+stepVal ;
                        min += stepVal ;
                }
            
                for (it = (*this)[currNode].noCapViolationCells.begin() ; it != (*this)[currNode].noCapViolationCells.end() ; ++it)
                {
                        double tmpValue = library.findMaxAvgDelay((*it)) / library.mapStandardLibraryCells[(*it)].leakagePower ;
                        double normalizedDelay = (library.findMaxAvgDelay((*it)) - minDelayAvg) / (maxDelayAvg - minDelayAvg) ;					
                        // store gate with all delay
                        if ( library.findMaxOutputCapacitance((*it)) > minTotalCap)
                        {
                                GateDelayStructure tmp ;
                                tmp.cellName = (*it) ;
                                tmp.avgDelay = normalizedDelay ;
                                allGates.push_back(tmp) ;
                        }
                        //---------------------------
					
                        for (int i = 0 ; i < Nsample ; ++i)
                                if (tmpValue >= region[i].minBound && tmpValue < region[i].maxBound)
                                        if (normalizedDelay >= minDelay && normalizedDelay <= maxDelay)
                                                if ( library.findMaxOutputCapacitance((*it)) > minTotalCap)
                                                {
                                                        GateDelayStructure tmpGateDelay ;
                                                        tmpGateDelay.cellName = (*it) ;
                                                        tmpGateDelay.avgDelay = tmpValue ;
                                                        region[i].cellNames.push_back( tmpGateDelay ) ;
                                                }
                }            
			
			
                // Sort each region (increasing)
                std::sort(allGates.begin() , allGates.end(), DelayComparison()) ;
			
                for (int i = 0 ; i < Nsample; ++i)
                        std::sort(region[i].cellNames.begin(), region[i].cellNames.end(), DelayComparison());
			
                // find the medium
                for (int i = 0 ; i < Nsample; ++i)
                {
                        if (!region[i].cellNames.empty())
                        {
                                int midIndex = ( region[i].cellNames.size() ) / 2 ;
                                samples.push_back(region[i].cellNames[midIndex].cellName) ;
                        }	
                }
			
                std::vector<std::string>::iterator itFind ;
                std::vector<RegionStruct>::iterator maxIndex;
			
                while ((int)samples.size() != Nsample)
                {
                        //cout << "Samples are not equal with Nsample" << endl ;
                        // find the region with higher number of gates
                        maxIndex = std::max_element(region.begin(), region.end(), RegionComparison()) ;
			cout<<"Max Index size is "<<(int)maxIndex->cellNames.size()<<endl;	
			cout<<"Min bound is "<<maxIndex->minBound<<endl;	
			cout<<"Max bound is "<<maxIndex->maxBound<<endl;	
                        for (int i = 0 ; i < (int)maxIndex->cellNames.size() ; ++i)
                        {
                                std::string tmpCell = maxIndex->cellNames[i].cellName ;
                                itFind = std::find(samples.begin(), samples.end(), tmpCell) ;
                                if (itFind == samples.end())
                                        samples.push_back(tmpCell) ;
                                if ((int)samples.size() == Nsample)//min
                                        break ;
                        }
                        maxIndex->cellNames.clear() ;
                }

                std::vector<GateDelayStructure>::iterator iterateCells ;
                std::vector<GateDelayStructure>::iterator lessThan = allGates.begin() ;
                std::vector<GateDelayStructure>::iterator greaterThan = allGates.begin();
		
                for (iterateCells = allGates.begin()  ; iterateCells != allGates.end() ; iterateCells++)
                {
                        if (iterateCells->avgDelay < minDelay)
                                lessThan++ ;
                        if (iterateCells->avgDelay < maxDelay)
                                greaterThan++ ;
                }
			
			
                lessThan-- ;
                bool isBegin = false ;
			
			
                while ((int)samples.size() != Nsample)
                {
                        if(greaterThan != allGates.end())
                        {
                                std::string maxCell = greaterThan->cellName ;
                                itFind = std::find(samples.begin(), samples.end(), maxCell) ;
				
                                if (itFind == samples.end())
                                        samples.push_back(maxCell) ;
                        }
                        if ((int)samples.size() == Nsample)
                                break ;	
				
				
                        if (!isBegin)
                        {
                                std::string minCell = lessThan->cellName ;
                                itFind = std::find(samples.begin(), samples.end(), minCell) ;	
				
                                if (itFind == samples.end())
                                        samples.push_back(minCell) ;
					
                                if ((int)samples.size() == Nsample)
                                        break ;	
                        }	
				
                        if (lessThan == allGates.begin() && greaterThan == allGates.end())
                                break ;

                        if (lessThan == allGates.begin())
                                isBegin = true ;
				
                        if (!isBegin)	
                                lessThan-- ;
                        if (greaterThan != allGates.end())
                                greaterThan++ ;
				
                }
                if ((int)samples.size() != Nsample)
                        equal = false ;
                else
                        equal = true ;
        }
}


void CircuitGraph::SampleGateNearby (vertex_descriptor currNode, std::string cellName, ExtendedLibParser& library, int Nsample,
                                        std::vector<std::string>& samples, double minDelay, double maxDelay, bool& equal)
										 
{
	double delay = library.findMaxAvgDelay(cellName) ;
	double minDelayFunc = delay - minDelay ;
        double maxDelayFunc = delay + maxDelay ;
        
        if (minDelayFunc<0)
                minDelayFunc = 0.0;
        if (maxDelayFunc > 1)
                maxDelayFunc = 1.0;
        
	this->stepSampleGateAngle (currNode, library, Nsample, samples, minDelayFunc, maxDelayFunc, equal) ;
}


void CircuitGraph::stepSampleGateAngle (vertex_descriptor currNode, ExtendedLibParser& library, int Nsample,
                                        std::vector<std::string>& samples, double minDelay, double maxDelay, bool& equal)
{
        samples.clear() ;
        this->sampleGateAngle (currNode, library, Nsample, samples, minDelay, maxDelay, equal) ;
}


void CircuitGraph::printOutEdgeProperty (vertex_descriptor& v)
{
	boost::graph_traits<CircuitGraph>::out_edge_iterator oi, oi_end ;
	
	for ( boost::tie(oi, oi_end) = boost::out_edges(v, (*this)) ; oi != oi_end ; ++oi )
        {
                cout << "Net Names: "<< (*this)[(*oi)].netName << endl ;
                cout << "ParasiticLoad: " << (*this)[(*oi)].netParasiticLoad << endl ;
                cout << (*this)[boost::source((*oi), (*this))].instanceName
                     << " ( "  << (*this)[(*oi)].sourcePinName << " )" 
                     << "=>"  << (*this)[target((*oi), (*this))].instanceName 
                     << " ( " << (*this)[(*oi)].targetPinName <<  " ) " << endl ;
        }
}


void CircuitGraph::fillPinTrans(vertex_descriptor currNode, 
                                ExtendedTimingParser& timing, 
                                ExtendedLibParser& library, 
                                std::map<std::string, double>& pinFallTrans,
                                std::map<std::string, double>& pinRiseTrans
        )
{
	pinFallTrans.clear() ;
	pinRiseTrans.clear() ;
	
	std::vector<LibParserPinInfo>::iterator pinIt ;
	

        for ( pinIt = library.mapStandardLibraryCells[(*this)[currNode].cellName].pins.begin() ;
              pinIt != library.mapStandardLibraryCells[(*this)[currNode].cellName].pins.end() ;
              ++pinIt)
        {
                if ((*pinIt).isInput)
                {
                        std::string instName = (*this)[currNode].instanceName ;
                        std::string pinName = (*pinIt).name ;
			
                        LibPinTimingInfo currTiming = timing.PinsTiming[instName + "/" + pinName] ;
                        pinFallTrans[pinName] = currTiming.fallTransition ;
                        pinRiseTrans[pinName] = currTiming.riseTransition ;
                }
	
        }
}


double CircuitGraph::calculateTotalOutputCap (vertex_descriptor currNode, ExtendedLibParser& library)
{

	boost::graph_traits<CircuitGraph>::out_edge_iterator oi, oi_end ;
	
	double netCap = 0.0 ;
	double inputCap = 0.0 ;
	bool valid = true ;
	
	for ( boost::tie(oi, oi_end) = boost::out_edges(currNode, (*this)) ; oi != oi_end ; ++oi )
	{
		std::string pinName = (*this)[(*oi)].targetPinName ;
		std::string targetCell = (*this)[boost::target((*oi), (*this))].cellName ;
		if(valid)
		{
			netCap +=  (*this)[(*oi)].netParasiticLoad ;
			valid = false ;
		}
		inputCap += library.getInputCapacitance(targetCell, pinName) ;	
	}
	
	return ( netCap + inputCap ) ;

}


void CircuitGraph::updateOutputTiming(vertex_descriptor currNode, vertex_descriptor nextNode,
                                      ExtendedLibParser& library, 
                                      ExtendedTimingParser& timing,
                                      double riseTT, double fallTT
        )
{

	boost::graph_traits<CircuitGraph>::out_edge_iterator oi, oi_end ;
	std::vector<LibParserPinInfo>::iterator pinIt ;
	
	for (boost::tie(oi, oi_end) = out_edges(currNode, (*this)) ; oi != oi_end ; oi++)
	{
		vertex_descriptor tmpVertex = boost::target( (*oi), (*this) ) ;
		
		if ( (*this)[tmpVertex].instanceName == (*this)[nextNode].instanceName )
		{
			std::string tmpName = (*this)[tmpVertex].instanceName +"/" + (*this)[(*oi)].targetPinName ;
			timing.PinsTiming[tmpName].riseTransition = riseTT ;
			timing.PinsTiming[tmpName].fallTransition = fallTT ;
		}
	}
	
}


void CircuitGraph::pathTiming(std::vector<vertex_descriptor>& path, ExtendedLibParser& library, 
                              ExtendedTimingParser& timing, 
                              double& fallSlew, double& riseSlew,
                              double& fallArrival, double& riseArrival,
                              double& totalCapViol, double& totalSlewViol,
                              double& totalSlackViol)
{
	
	std::vector<vertex_descriptor>::iterator currCell ;
	
	double totalFallArrival, totalRiseArrival  = 0.0;
	
	totalCapViol = 0.0 ;
	totalSlewViol = 0.0 ;
	totalSlackViol = 0.0 ;
        /*
          cout<<"In the path timing function...."<<endl;
          for ( currCell = path.begin() ; currCell != path.end() ; ++currCell)
          {
          cout<<*currCell<<"\t";
          cout<<(*this)[*currCell].cellName<<"\t";
          }
          cout<<endl;
        */
        // Iterate over all cells

        int pathNumber = 0;
	for ( currCell = path.begin() ; currCell != path.end() ; ++currCell)
	{
                
                std::map<std::string, double>::iterator transIt ;
		
		std::map<std::string, double> pinFallTrans, pinRiseTrans ;
		
		bool valid ;
		
		// Find the output capacitance of a cell
		double outCap = calculateTotalOutputCap ((*currCell), library) ;
		
                //cout<<"node name in path is "<<*currCell<<endl;
                //cout<<"Cell name is "<<(*this)[(*currCell)].cellName<<endl;
		double cellCapViol = std::max(0.0, 
                                              outCap - library.findMaxOutputCapacitance((*this)[(*currCell)].cellName) ) ;
                
		totalCapViol += cellCapViol ;
		
		(*this)[(*currCell)].Cap_Violation = cellCapViol ;
		
		// Fall Input Transition => Rise Delay, Rise Transition-------------------------------------
		
		this->fillPinTrans((*currCell), timing, library, pinFallTrans, pinRiseTrans) ;
		
		double cellTransViol = 0.0;
		
		for (transIt = pinFallTrans.begin(); transIt != pinFallTrans.end() ; ++transIt)
		{
			cellTransViol += std::max( 0.0, (*transIt).second - library.maxTransition ) ;
		}
		
		for (transIt = pinRiseTrans.begin(); transIt != pinRiseTrans.end() ; ++transIt)
		{
			cellTransViol += std::max( 0.0, (*transIt).second - library.maxTransition ) ;
		}
		
		(*this)[(*currCell)].Slew_Violation = cellTransViol ;
		
		// Find rise transition and rise delay
		double riseTT = library.maxRiseTransition ( (*this)[(*currCell)].cellName, pinFallTrans, outCap, valid ) ;
		double riseDelay = library.maxRiseDelay ( (*this)[(*currCell)].cellName, pinFallTrans, outCap, valid ) ;
		//------------------------------------------------------------------------------------------
		
		
		// Rise Input Transition => Fall Delay, Fall Transition-------------------------------------
		
		// Find fall transition and fall delay
		double fallTT = library.maxFallTransition ( (*this)[(*currCell)].cellName, pinRiseTrans, outCap, valid) ;
		double fallDelay = library.maxFallDelay ( (*this)[(*currCell)].cellName, pinRiseTrans, outCap, valid ) ;
		//------------------------------------------------------------------------------------------
	
		totalFallArrival = totalRiseArrival + riseDelay ;
		totalRiseArrival = totalFallArrival + fallDelay ;
		
		// Update the output pin timing info
		if ( currCell+1 != path.end() )
			this->updateOutputTiming((*currCell), *(currCell+1), library, timing,
                                                 riseTT, fallTT) ;
		else
		{
			fallSlew = fallTT ;
			riseSlew = riseTT ;
			fallArrival = totalFallArrival ; 
			riseArrival = totalRiseArrival ;
		}
	
		string tmpName = (*this)[(*currCell)].cellName + "/" + "o" ;
		
		if (pathNumber == (int)path.size() - 1)
		{
			totalSlackViol += timing.PinsTiming[tmpName].riseSlack ;
			totalSlackViol += timing.PinsTiming[tmpName].fallSlack ;
			(*this)[(*currCell)].Slack_Violation = totalSlackViol ;
		}
		pathNumber++ ;
	}

}


void CircuitGraph::updateConnectivity (std::vector<netConnectivity>& netArr, std::map<std::string, double>& parasiticLoad)
{
	std::vector<netConnectivity>::iterator it ;
	
	for (it =  netArr.begin() ; it != netArr.end() ;  it++)
	{
		for (int i = 0 ; i < (int)(*it).targetVertices.size() ; i++ )
		{
			netProperty tmpNet ;
			tmpNet.netName = (*it).netName ;
			tmpNet.netParasiticLoad = parasiticLoad[(*it).netName] ;
			tmpNet.sourcePinName = (*it).sourcePin ;
			tmpNet.targetPinName = (*it).targetPins[i] ;
			
			boost::add_edge ((*it).sourceVertex, (*it).targetVertices[i], tmpNet, (*this)) ;
		}
		
	}
	
	//netArr.clear() ;
}


double CircuitGraph::accumTotalLeakage (std::map <std::string, LibParserCellInfo>& standardCells)
{
	boost::graph_traits<boostGraph>::vertex_iterator vi, vi_end ;
	double totalLeakage = 0.0 ;
	
	for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi)
	{
		if ((*this)[(*vi)].gateType == Combinational || (*this)[(*vi)].gateType == Sequential)
		{
			//cout << "Gate: " << (*this)[(*vi)].cellName << "=> leakage: " << standardCells[(*this)[(*vi)].cellName].leakagePower << endl ;
			totalLeakage += standardCells[(*this)[(*vi)].cellName].leakagePower ;
		}
	}
	
	return totalLeakage ;
}


void CircuitGraph::findAllPaths (vertex_descriptor target, 
                                 std::vector<vertex_descriptor>& visited, std::vector< std::vector<std::string> >& paths)
{
	vertex_descriptor back = visited.back();
	
	boost::graph_traits<CircuitGraph>::adjacency_iterator ai, ai_end ;
	
	for ( boost::tie(ai, ai_end) = boost::adjacent_vertices(back, (*this) ) ; ai != ai_end; ++ai )
	{
		if ( find (visited.begin(), visited.end(), (*ai) ) != visited.end() ) continue ;
		
		if ((*ai) == target)
		{
			visited.push_back((*ai)) ;
			vector <std::string> tmpPath ;
			
			for (int i = 0 ; i < (int)visited.size() ; ++i)
				tmpPath.push_back( boost::get( &gateProperty::instanceName, (*this) , visited[i] ) ) ;
			
			paths.push_back(tmpPath) ;
			
			visited.erase ( visited.begin() +  ( visited.size() - 1 ) ) ;
			
			break ;
		}
	}
	
	
	for ( boost::tie(ai, ai_end) = boost::adjacent_vertices(back, (*this) ) ; ai != ai_end; ++ai )
	{
		if (find (visited.begin(), visited.end(), (*ai)) != visited.end()  || (*ai) == target )
			continue ;
		visited.push_back ((*ai)) ;
		this->findAllPaths (target, visited, paths) ;
		visited.erase ( visited.begin() +  (visited.size() - 1)) ;
	}
}


int CircuitGraph::findVertexIndex (std::string name)
{
	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	int index = 0;
	bool find = false ;
	for ( boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi , ++index)
	{
		if ((*this)[(*vi)].instanceName ==  name)
		{	
			find = true ;
			break ;
		}
	}
	
	if (find)
		return index ;
	else
		return -1 ;
	
}


void CircuitGraph::fillNoCapViolationCells (ExtendedLibParser& library)
{
	
	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	std::vector<std::string>::iterator it, it_end ;
	
	double maxCap = 0.0 ;
	
	for ( boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end ; ++vi )
	{
		it_end = (*this)[(*vi)].listOfCells.end() ;
		
		for ( it = (*this)[(*vi)].listOfCells.begin(); it != it_end ; ++it )
		{
			for (int i = 0 ; i < (int) library.mapStandardLibraryCells[(*it)].pins.size() ; ++i)
			{
				if (!library.mapStandardLibraryCells[(*it)].pins[i].isInput)
					maxCap = library.mapStandardLibraryCells[(*it)].pins[i].maxCapacitance ;
			}
			
			//if ((*this)[(*vi)].instanceName == "g60106_u0")
			//	cout << "min output cap " <<  (*this)[(*vi)].minOutCapacitance << endl;
			if (maxCap >= (*this)[(*vi)].minOutCapacitance)
			{
				(*this)[(*vi)].noCapViolationCells.push_back((*it)) ;
				
				double leakage = library.mapStandardLibraryCells[(*it)].leakagePower ;
				double avgDelay = library.findMaxAvgDelay((*it));
				double delayLeakage = avgDelay / leakage ;
				
				(*this)[(*vi)].minDelayAvg = std::min((*this)[(*vi)].minDelayAvg, avgDelay) ;
				(*this)[(*vi)].maxDelayAvg = std::max((*this)[(*vi)].maxDelayAvg, avgDelay) ;
				
				(*this)[(*vi)].minDelayLeakage = std::min((*this)[(*vi)].minDelayLeakage, delayLeakage) ;
				(*this)[(*vi)].maxDelayLeakage = std::max((*this)[(*vi)].maxDelayLeakage, delayLeakage) ;
				
			}
		}
		
		//if ((*this)[(*vi)].instanceName == "g60106_u0")
                //	cout << "number of cells " <<  (*this)[(*vi)].noCapViolationCells.size() << endl;
		
	}	
}


bool CircuitGraph::isCover (std::string firstType, std::string secondType, double outCap, ExtendedLibParser& library, bool& isValidComp)
{
	
	LibParserCellInfo firstCell  = library.mapStandardLibraryCells[firstType] ; 
	LibParserCellInfo secondCell = library.mapStandardLibraryCells[secondType] ;
	
	std::vector<LibParserTimingInfo>::iterator timingItFirst, timingItSecond ;
	std::vector<LibParserLUT>::iterator LutItFirst, LutItSecond ;
	
	std::vector<double>::iterator transIt ;
	
	bool isCover = true ;
	
	for (timingItFirst = firstCell.timingArcs.begin() ; timingItFirst != firstCell.timingArcs.end() ; ++timingItFirst)
	{
	
		for (timingItSecond = secondCell.timingArcs.begin() ; timingItSecond != secondCell.timingArcs.end() ; ++timingItSecond)
		{
			if ( 
				(*timingItFirst).fromPin != (*timingItSecond).fromPin
				|| 
				(*timingItFirst).toPin != (*timingItSecond).toPin
				
                                )
				continue ;
				
			else
				break ;
				
		}
		
		
		// Check Fall Delay
		
		LibParserLUT fallDelayFirst = (*timingItFirst).fallDelay ;
		LibParserLUT fallDelaySecond = (*timingItSecond).fallDelay ;
		
		for (transIt = fallDelayFirst.transitionIndices.begin() ; transIt != fallDelayFirst.transitionIndices.end() ; ++transIt)
		{
			double firstDelay, secondDelay ;
			bool firstValid, secondValid ;
			
			firstDelay = fallDelayFirst(outCap, (*transIt), firstValid ) ;
			secondDelay = fallDelaySecond(outCap, (*transIt), secondValid ) ;
			
			
			if (!firstValid || !secondValid)
			{
				isValidComp = false ;
				return false ;
			}
			
			if (firstDelay > secondDelay)
				isCover = false ;
		}
		
		
		
		// Check Rise Delay
		
		LibParserLUT riseDelayFirst = (*timingItFirst).riseDelay ;
		LibParserLUT riseDelaySecond = (*timingItSecond).riseDelay ;
		
		for (transIt = riseDelayFirst.transitionIndices.begin() ; transIt != riseDelayFirst.transitionIndices.end() ; ++transIt)
		{
			double firstDelay, secondDelay ;
			bool firstValid, secondValid ;
			
			firstDelay = riseDelayFirst(outCap, (*transIt), firstValid ) ;
			secondDelay = riseDelaySecond(outCap, (*transIt), secondValid ) ;
			
			if (firstDelay > secondDelay)
				isCover = false ;
		}
	
	
	}
	
	isValidComp = true ;
	
	if (isCover && firstCell.leakagePower <= secondCell.leakagePower)
		return true ;
	else
		return false ;
	
}


bool CircuitGraph::isCoverRange (std::string firstType, std::string secondType, double minCap, double maxCap
                                 , int stepsNum, ExtendedLibParser& library, bool& isValidComp)
{
	double step = (maxCap - minCap) / (double) stepsNum ;
	
	bool result ;
	double outCap = minCap ;
	bool valid ;
	for (int i = 0 ; i < stepsNum ; i++)
	{
		result = isCover(firstType, secondType, outCap, library, valid) ;
		
		if (!result)
		{
			isValidComp = valid ;
			return false ;
		}
		if (!valid)
		{
			isValidComp = false ;
			return false ;
		}
			
		outCap += step ;
	}

	isValidComp = true ;
	return true ;

}


void CircuitGraph::pruneGate (vertex_descriptor currNode, ExtendedLibParser& library)
{

	std::vector<std::string>::iterator cellIt1, cellIt2 ;
	std::vector<std::string> tmp ;
	bool intResult, finalResult ;
	
	for ( cellIt1 = (*this)[currNode].noCapViolationCells.begin() ; cellIt1 != (*this)[currNode].noCapViolationCells.end() ; ++cellIt1 )
	{
		finalResult = false ;
		for (cellIt2 = (*this)[currNode].noCapViolationCells.begin() ; cellIt2 != (*this)[currNode].noCapViolationCells.end() ; ++cellIt2 )
		{
			if ((*cellIt1) == (*cellIt2))
				continue ;
				
			double tmp = std::min(library.findMaxOutputCapacitance((*cellIt1)) , library.findMaxOutputCapacitance((*cellIt2))) ;
			double maxCap = std::min(tmp, (*this)[currNode].maxOutCapacitance) ;
			bool isValidComp ;
			intResult = this->isCoverRange((*cellIt2), (*cellIt1), (*this)[currNode].minOutCapacitance, maxCap, 5, library, isValidComp) ;
			if (intResult)
				finalResult = true ;
		}
		if (!finalResult)
			tmp.push_back((*cellIt1)) ;
	}

	(*this)[currNode].noCapViolationCells.clear() ;
	(*this)[currNode].noCapViolationCells = tmp ;
}								


void CircuitGraph::fillOrderedSamples( std::vector<std::pair<std::string, double> > & candidates, double min, double max, std::vector<std::string>& sample)
{
	double sum = 0.0 ;
        //cout<<"size of candidates "<<candidates.size()<<endl;
	for (int i = 0 ; i < (int)candidates.size(); ++i)
		sum += candidates[i].second ;
	double avg = sum / (double)candidates.size() ;
	
	sample.clear() ;
	std::vector<std::pair<std::string, double> > sortedCandidates ;
	
	sortedCandidates.push_back(candidates[0]) ; // insert first candidate
	int j ;
	for (int i = 1 ; i < (int)candidates.size(); ++i)
	{
		
		for (j = 0 ; j < (int)sortedCandidates.size(); ++j)
		{
			if ( std::abs(candidates[i].second - avg) > std::abs(sortedCandidates[j].second - avg) )
				continue ;
			break ;
		}
		sortedCandidates.insert(sortedCandidates.begin() + j, candidates[i]) ;
	}
	
	for (int i = 0 ; i < (int)sortedCandidates.size(); ++i)
		sample.push_back(sortedCandidates[i].first) ;
}


void CircuitGraph::sampleGateLeakage (vertex_descriptor currNode, ExtendedLibParser& library, int Nsample, std::vector<std::string>& samples)
{

        samples.clear();

	if ( (*this)[currNode].gateType == Combinational )
	{
	
                std::vector<std::string>::iterator it ;
	
                double max =  0.0 ;
                double min = 100000000.00 ;
                for (it = (*this)[currNode].noCapViolationCells.begin() ; it != (*this)[currNode].noCapViolationCells.end() ; ++it)
                {
                        double tmpLeakage = library.mapStandardLibraryCells[(*it)].leakagePower ;
                        max  = std::max(max, tmpLeakage) ;
                        min = std::min(min, tmpLeakage) ;
                }
	
                double stepLeakage = ((max+0.1) - min) / (double) Nsample ;
	
                std::vector<std::vector<std::pair<std::string, double> > > region(Nsample) ;
        
                std::vector<std::pair<double, double> > range (Nsample) ;
	
                for (int i = 0 ; i < (int)range.size() ; ++i)
                {
                        range[i] = std::make_pair(min, min+stepLeakage) ;
                        min += stepLeakage ;
                }
        
                for (it = (*this)[currNode].noCapViolationCells.begin() ; it != (*this)[currNode].noCapViolationCells.end() ; ++it)
                {
                        double tmpLeakage = library.mapStandardLibraryCells[(*it)].leakagePower ;
                        for (int i = 0 ; i < (int)range.size() ; ++i)
                                if (tmpLeakage >= range[i].first && tmpLeakage < range[i].second)
                                        region[i].push_back(std::make_pair( (*it), library.mapStandardLibraryCells[(*it)].leakagePower ) ) ;
                }
	
                std::vector<std::vector<std::string> > orderedSample ;
	
                for (int i = 0 ; i < (int)range.size(); ++i)
                {
                        if (region[i].size() != 0)
                        {
                                std::vector<std::string> tmpVector ;
                                this->fillOrderedSamples(region[i], range[i].first, range[i].second, tmpVector) ;     
                                orderedSample.push_back(tmpVector) ;
                        }
                }
	
	
                for (int i = 0 ; i < (int)orderedSample.size(); ++i)
                {
                        if (orderedSample[i].size() != 0)
                                samples.push_back(orderedSample[i][0]);
                }
	
                bool firstIter = true ;
	
                while ((int)samples.size() != Nsample)
                {
                        int sampleIndex = 0 ;
                        if (firstIter)
                        {
                                sampleIndex = this->findMaxOrderedIndex(orderedSample) ;
                                firstIter = false;
                        }
		
                        for (int i = 1 ; i < (int)orderedSample[sampleIndex].size(); ++i)
                        {
                                samples.push_back(orderedSample[sampleIndex][i]) ;
                                if ((int)samples.size() == Nsample)
                                        break ;
                        }
		
                        orderedSample.erase(orderedSample.begin() + sampleIndex) ;
                        firstIter = true ;
                }
	}
}


void CircuitGraph::sampleGateDelay (vertex_descriptor currNode, ExtendedLibParser& library, int Nsample, std::vector<std::string>& samples)
{
	std::vector<std::string>::iterator it ;
	samples.clear() ;
	
	if ( (*this)[currNode].gateType == Combinational )
	{
	
		double max =  0.0 ;
		double min = 100000000.00 ;
        
		for (it = (*this)[currNode].noCapViolationCells.begin() ; it != (*this)[currNode].noCapViolationCells.end() ; ++it)
		{
       	         
			double tmpDelay = library.findMaxAvgDelay((*it)) ;
			max  = std::max(max, tmpDelay) ;
			min = std::min(min, tmpDelay) ;
		}
	
		double stepDelay = ((max+0.1) - min) / (double) Nsample ;
	
		std::vector<std::vector<std::pair<std::string, double> > > region(Nsample) ;
	
		std::vector<std::pair<double, double> > range (Nsample) ;
        
		for (int i = 0 ; i < (int)range.size() ; ++i)
		{
			range[i] = std::make_pair(min, min+stepDelay) ;
			min += stepDelay ;
		}
	
		for (it = (*this)[currNode].noCapViolationCells.begin() ; it != (*this)[currNode].noCapViolationCells.end() ; ++it)
		{
			double tmpDelay = library.findMaxAvgDelay((*it)) ;
		
			for (int i = 0 ; i < (int)range.size() ; ++i)
				if (tmpDelay >= range[i].first && tmpDelay < range[i].second)
					region[i].push_back(std::make_pair( (*it), tmpDelay) ) ;
		}
	
		std::vector<std::vector<std::string> >  orderedSample ;
	
		for (int i = 0 ; i < (int)range.size(); ++i)
		{
			if (region[i].size() != 0)
			{
				std::vector<std::string> tmpVector ;
                                this->fillOrderedSamples(region[i], range[i].first, range[i].second, tmpVector) ;     
                                orderedSample.push_back(tmpVector) ;
                        }
		}
	
	
		for (int i = 0 ; i < (int)orderedSample.size(); ++i)
		{
			if (orderedSample[i].size() != 0)
				samples.push_back(orderedSample[i][0]) ;
		}

		bool firstIter = true ;
	
		while ((int)samples.size() != Nsample)
		{
			int sampleIndex = 0 ;
		
			if (firstIter)
			{	
				sampleIndex = this->findMaxOrderedIndex(orderedSample) ;
				firstIter = false ;
			}
		
			for (int i = 1 ; i < (int)orderedSample[sampleIndex].size() ; ++i)
			{
				samples.push_back(orderedSample[sampleIndex][i]) ;
				if ((int)samples.size() == Nsample)
                                        break ;
			}
		
			orderedSample.erase(orderedSample.begin() + sampleIndex) ;
			firstIter = true ;
		}
	}
}


int CircuitGraph::findMaxOrderedIndex (std::vector<std::vector<std::string> >& ordered)
{
	int index = -1 ;
	int maxSize = 0 ;
	
	for (int i = 0 ; i < (int) ordered.size(); i++)
	{
		if ((int)ordered[i].size() > maxSize)
		{
			maxSize = ordered[i].size() ;
			index = i ;
		}
	}
	
	return index ;
}


void CircuitGraph::sampleGateAngle (vertex_descriptor currNode, ExtendedLibParser& library, int Nsample, std::vector<std::string>& samples
                                    , double minDelay, double maxDelay, bool& equal)
{
        
        samples.clear();
        double minTotalCap = this->findMinTotalOutputCapacitance(currNode, library) ;
        //cout << "min total capacitance: " << minTotalCap << endl ;
        
        std::vector<std::string>::iterator it ;
        
        if ( (*this)[currNode].gateType == Combinational )
        {

                double max =  0.0 ;
                double min = 100000000.00 ;
                
                double minDelayAvg = 10000000.0 ;
                double maxDelayAvg = 0.0 ;
                
                for (it = (*this)[currNode].noCapViolationCells.begin() ; it != (*this)[currNode].noCapViolationCells.end() ; ++it)
                {
                        double tmpValue = library.findMaxAvgDelay((*it)) / library.mapStandardLibraryCells[(*it)].leakagePower ;
                        max  = std::max(max, tmpValue) ;
                        min = std::min(min, tmpValue) ;
                        
                        minDelayAvg = std::min(minDelayAvg, library.findMaxAvgDelay((*it))) ;
                        maxDelayAvg = std::max(maxDelayAvg, library.findMaxAvgDelay((*it))) ;
                        
                }
                
                double stepVal = ((max+0.1) - min) / (double) Nsample ;
                
                std::vector<std::vector<std::pair<std::string, double> > > region(Nsample) ;
                
                std::vector<std::pair<double, double> > range (Nsample) ;
                
                for (int i = 0 ; i < (int)range.size() ; ++i)
                {
                        range[i] = std::make_pair(min, min+stepVal) ;
                        min += stepVal ;
                }
                
                for (it = (*this)[currNode].noCapViolationCells.begin() ; it != (*this)[currNode].noCapViolationCells.end() ; ++it)
                {
                        double tmpValue = library.findMaxAvgDelay((*it)) / library.mapStandardLibraryCells[(*it)].leakagePower ;
                        double normalizedDelay = (library.findMaxAvgDelay((*it)) - minDelayAvg) / (maxDelayAvg - minDelayAvg) ;
                        
                        for (int i = 0 ; i < (int)range.size() ; ++i)
                                if (tmpValue >= range[i].first && tmpValue < range[i].second)
                                        if (normalizedDelay >= minDelay && normalizedDelay <= maxDelay)
                                                if ( library.findMaxOutputCapacitance((*it)) > minTotalCap)
                                                {
                                                        region[i].push_back( std::make_pair( (*it), tmpValue) ) ;
                                                }
                }
                
                std::vector<std::vector<std::string> > orderedSample ;
                
                for (int i = 0 ; i < (int)range.size(); ++i)
                {
                        if (region[i].size() != 0)
                        {
                                std::vector<std::string> tmpVector ;
                                this->fillOrderedSamples(region[i], range[i].first, range[i].second, tmpVector) ;     
                                orderedSample.push_back(tmpVector) ;
                        }
                }
                
                for (int i = 0 ; i < (int)orderedSample.size(); ++i)
                {
                        if (orderedSample[i].size() != 0)
                                samples.push_back(orderedSample[i][0]) ;
                }
                
                bool firstIter = true ;
                
                while ((int)samples.size() != Nsample)
                {
                        if ((int)orderedSample.size() == 0)
                                break ;
                        
                        int sampleIndex = 0 ; 
                        if (firstIter)
                        {
                                sampleIndex = this->findMaxOrderedIndex(orderedSample) ;
                                firstIter = false ;
                        }
                        
                        for (int i = 1 ; i <  (int)orderedSample[sampleIndex].size() ; ++i)
                        {
                                samples.push_back(orderedSample[sampleIndex][i]) ;
                                if ((int)samples.size() == Nsample)
                                        break ;
                        }
                        
                        orderedSample.erase(orderedSample.begin() + sampleIndex) ;
                        firstIter = true ;
                        
                }
                
                if ((int)samples.size() != Nsample)
                        equal = false ;
                else
                        equal = true ;
        }
}


void CircuitGraph::updateMinMaxOutputCap (ExtendedLibParser& library, StoreOutCapacitance storeStruct, ostream& out, bool writeFile)
{
	double minCap, maxCap ;
	
	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	
	out << "Cell Name\t" << "Min Cap\t" << "Max Cap\t" << endl ;
	
	for (boost::tie(vi, vi_end) = boost::vertices((*this)) ; vi != vi_end; ++vi)
	{
		minCap = maxCap = 0.0 ;
		
		if ( (*this)[(*vi)].gateType == Combinational )
		{
			(*this).findRangeOutputCap ((*vi), minCap, maxCap, library) ;
			
			(*this)[(*vi)].minOutCapacitance = minCap ; 
			(*this)[(*vi)].maxOutCapacitance = maxCap ;
			
			if (writeFile)
			{
#ifdef DEBUG
                                cout << (*this)[(*vi)].instanceName << "\t" << minCap << "\t" << maxCap << endl ;
#endif
				
				storeStruct.StoreFunction (out, (*this)[(*vi)].instanceName, minCap, maxCap) ;
			}
		}
	}
}


void CircuitGraph::findRangeOutputCap (vertex_descriptor curNode, double& minCap, double& maxCap, ExtendedLibParser& library)
{
	boost::graph_traits<CircuitGraph>::out_edge_iterator oi, oi_end ;
	std::pair<double, double> result ;
	double netParasitic = 0.0 ;
	vertex_descriptor tmpVertex ;
	for (boost::tie(oi, oi_end) = boost::out_edges(curNode, (*this)) ; oi != oi_end ; ++oi)
	{
		netParasitic = (*this)[(*oi)].netParasiticLoad ;
		tmpVertex = target((*oi), (*this)) ;
		
#ifdef DEBUG
                cout << (*this)[tmpVertex].footPrint << "\t" << (*this)[(*oi)].targetPinName << endl ;
#endif
		
		if ((*this)[tmpVertex].gateType != PrimaryOutput)
			result = library.pinCapacitance( (*this)[tmpVertex].footPrint, (*this)[(*oi)].targetPinName ) ;
		else
			result = std::make_pair<double, double>( (*this)[tmpVertex].outCapacitance, (*this)[tmpVertex].outCapacitance) ;
	}
	
	minCap = result.first + netParasitic; 
	maxCap = result.second + netParasitic;
}


void CircuitGraph :: showNodesUnderInspection()
{
        cout<<"Nodes under inspection are "<<endl;
        vector<vertex_descriptor>::iterator it;
        for(it = this->nodes_under_inspection.begin(); it != this->nodes_under_inspection.end(); it++)
                cout<<"Node "<< *it << "\t" << (*this)[*it].instanceName
                    << "\t" << (*this)[*it].Slack_Violation
                    << "\t" << (*this)[*it].Slew_Violation
                    << "\t" << (*this)[*it].Cap_Violation << endl;
}

template <typename T, typename Bundle>
std::vector<vertex_descriptor> CircuitGraph::getVerticesWithProperty(T property, T Bundle::* p)
{
	boost::graph_traits<CircuitGraph>::vertex_iterator vi, vi_end ;
	std::vector<vertex_descriptor> tmp ;
	for (boost::tie(vi, vi_end) = boost::vertices((*this)); vi != vi_end ; ++vi)
	{
		if ( boost::get(p, (*this), *vi) == property)
			tmp.push_back( (*vi) ) ;
	}
	
	return tmp ;
	
}


template <typename T, typename Bundle>
std::vector<edge_descriptor> CircuitGraph::getEdgesWithProperty(T property, T Bundle::* p)
{
	boost::graph_traits<CircuitGraph>::edge_iterator ei, ei_end ;
	std::vector<edge_descriptor> tmp ;
	for (boost::tie(ei, ei_end) = boost::edges((*this)); ei != ei_end ; ++ei)
	{
		if ( boost::get(p, (*this), *ei) == property)
			tmp.push_back( (*ei) ) ;		
	}
	return tmp ;
}


template <typename T, typename Bundle>
inline void CircuitGraph::printGateProperty (T Bundle::* p)
{
	boost::graph_traits<CircuitGraph>::vertex_iterator vi,vi_end;
        for (boost::tie(vi,vi_end) = boost::vertices((*this)); vi != vi_end; ++vi)
                cout<< "Vertices: \n" << boost::get(p, (*this), *vi) << endl;
}


template <typename T, typename Bundle>
inline void CircuitGraph::printNetProperty (T Bundle::* p)
{
	boost::graph_traits<CircuitGraph>::edge_iterator vi,vi_end;
        for (boost::tie(vi,vi_end) = boost::edges((*this)); vi != vi_end; ++vi)
                cout<< "Edges: \n" << boost::get(p, (*this), *vi) << endl;
}


void CircuitGraph::operator << (const vertex_descriptor& in)
{
	cout << "Cell Name: " << (*this)[in].cellName << endl ;
	cout << "Instance Name: " << (*this)[in].instanceName << endl ;
	
	switch ( (*this)[in].gateType )
	{
		case 0:
			cout << "Gate Type: Primary Input" << endl ;
			break;
		case 1:
			cout << "Gate Type: Primary Output" << endl ;
			break;
		case 2:
			cout << "Gate Type: Combinational" << endl ;
			break;
		case 3:
			cout << "Gate Type: Sequential" << endl ;
			break ;
	}
	cout << endl << endl ;
}
		
		
void CircuitGraph::operator << (const edge_descriptor& in)
{
	cout << "Net Name: " << (*this)[in].netName << endl ;
	cout << "Source Gate: " << (*this)[boost::source( in, (*this) )].instanceName << endl ;
	cout << "Target Gate: " << (*this)[boost::target( in, (*this) )].instanceName << endl;
	cout << "Source Pin: " << (*this)[in].sourcePinName << endl ;
	cout << "Target Pin: " << (*this)[in].targetPinName << endl ;
	
	cout  << endl << endl ;
}


double readMapSecond(std::map<std::string, double>& inputMap)
{
	std::map<std::string, double>::iterator it ;
	
	for (it = inputMap.begin() ; it != inputMap.end(); ++it)
	{
		cout << "First: " << (*it).first << endl ;
		cout << "Second: "	<< (*it).second << endl ;
	}
	return 0 ;
}
